package 刷题.速成清单;

import java.util.Scanner;

public class 小明的背包1 {
    // 定义数组 w 用于存储每个物品的体积，数组大小初始化为 105
    static int[] w = new int[105];
    // 定义数组 v 用于存储每个物品的价值，数组大小初始化为 105
    static int[] v = new int[105];

    public static void main(String[] args) {
        // 创建 Scanner 对象，用于从标准输入读取数据
        Scanner in = new Scanner(System.in);
        // 读取商品的数量 N
        int N = in.nextInt();
        // 读取小明背包的总容量 V
        int V = in.nextInt();

        // 循环读取每个物品的体积和价值，并存储到 w 和 v 数组中
        for (int i = 1; i <= N; i++) {
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }

        // 创建二维数组 dp，dp[i][j] 表示考虑前 i 个物品，背包容量为 j 时能获得的最大价值
        int[][] dp = new int[N + 1][V + 1];
        // 初始化边界条件，当没有物品（i = 0）且背包容量为 0 时，最大价值为 0
        dp[0][0] = 0;

        // 动态规划过程，外层循环遍历每个物品
        for (int i = 1; i <= N; i++) {
            // 内层循环遍历每个背包容量
            for (int j = 1; j <= V; j++) {
                // 判断当前物品的体积是否小于等于当前背包容量
                if (w[i] <= j) {
                    // 若可以放入当前物品，取不放入和放入该物品两种情况的最大价值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                } else {
                    // 若当前物品体积大于背包容量，不能放入，最大价值等于前 i - 1 个物品的最大价值
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        // 输出考虑所有物品，背包容量为 V 时能获得的最大价值
        System.out.println(dp[N][V]);
    }
}
